Imaging and video coding standards (such as JPEG, MPEG, and H.26x) have evolved greatly in the past decade. In the early stages, the main requirements and objective for such video coding standards were compression efficiency. With the expansion of markets, video coding standards began to require other attractive features in addition to high compression efficiency. One of the most desired features is image quality scalability. In most cases, image quality scalability is achieved by a layered video coding technique. This includes a base layer and subsequent separate enhancement layers. The base layer is the minimum of coded data sufficient to generate a visible video sequence. An existing video coding standard can be the base layer. Each enhancement layer contains data to improve the quality of the decoded image over the base layer and preceding enhancement layers. In general, these enhancement layers refine the values of transformed coefficients. For example, suppose the desired transformed coefficient to be coded is 25. A scalable formation of 25 can be achieved by coding 16 in the base layer, 8 in the first enhancement layer and 1 in the second enhancement layer.
There are two main objectives in processing an enhancement layer: propagation of significance; and refinement of magnitude. In propagation of significance, the enhancement layer coder seeks a non-significant coefficient. Such a non-significant coefficient is not yet coded in preceding layers. The coder codes the location of the coefficient and its magnitude if necessary. Because the significance of the coefficient will greatly depend on the neighboring coefficients and the location of the coefficient can be encoded in various ways, it is relatively easy to efficiently code the propagation of significance in variable length coding (VLC).
In the refinement of magnitude, the enhancement layer coder seeks a significant coefficient which is already coded in preceding layers. Unlike the propagation of significance, the refinement of magnitude is almost independent of the status of neighboring coefficients or the coefficient itself. In most cases, the coder will generate a binary flag indicating whether this coefficient will be refined or not. This is called a refinement flag. Depending on the method of refinement, the sign of refinement (called refinement sign) and the magnitude of refinement (called refinement magnitude especially if greater than 1) are also coded. Many binary symbols need to be coded in this refinement of magnitude process. Efficient coding of such binary symbols is important to the quality scalability with a desired compression efficiency.
A VLC technique is generally employed to improve the coding efficiency. A shorter code is assigned to more frequent symbols, and a longer code to less frequent symbols. Thus a 1 bit codeword will be assigned to a symbol even if that symbol appears with extremely high probability (e.g. nearly 100%). Therefore, it is believed variable length coding of binary symbols is inefficient. The JPEG 2000 standard employs arithmetic coding technology to address this problem. The JPEG 2000 standard is a known as still image coding standard with quality and other various scalability features. However, it is known that arithmetic coding technology is much more complex computationally than VLC technology. Therefore, some VLC based technique that would efficiently code the refinement symbols is desired.
FIG. 1 illustrates flowchart of a typical refinement symbol coding technique 100 using VLC. Technique 100 begins with start block 101. Block 102 scans the coefficients and identifies those to be coded using this process. Block 103 divides each refinement coefficient into several informational elements. As noted above these informational elements typically include refinement flag, refinement sign and refinement magnitude. Block 104 groups the current binary informational element symbols. For the first iteration, the current binary informational element symbols is the first binary informational element symbols. Block 105 codes the grouped symbols using a known VLC technique. Block 106 codes any remaining fractional symbols. Test block 107 determines if there are remaining binary informational symbols. If there are remaining binary informational symbols (Yes at test block 107), then block 108 starts the next binary informational symbols. Technique 100 returns to block 104 to start coding this next binary informational symbol. If there are no remaining binary informational symbols (No at test block 107), then block 109 uses a VLC technique to code any remaining non-binary elements. Technique 100 ends at end block 110.
FIG. 2 illustrates an example of the conventional VLC method to code refinement symbols. This example assumes that a refinement flag, a refinement sign and a refinement magnitude are to be coded. The first column of the first half is a coefficient index from 0 to 6. The second column of the first half is the coefficient data already coded in preceding layers. The third column of the first half is the refinement coefficients to be coded in the current layer. After coding the current layer, the refined coefficients data will be the summation of the second column and the third column. The second half shows the coding of these refinement coefficients. The refinement coefficients are divided into the following three elements: refinement flag (fourth column, binary), refinement sign (fifth column, binary), and refinement magnitude (sixth column, multinary).
For coefficient index 0 the refinement coefficient of the current layer is 0. This is coded using a 0 refinement flag. No refinement sign or refinement magnitude are coded in this case.
For coefficient index 1 the refinement coefficient of the current layer is 2. This is coded using a 1 refinement flag, a 0 refinement sign indicating a positive sign and a refinement magnitude of 2.
For coefficient index 2 the refinement coefficient of the current layer is 1. This is coded using a 1 refinement flag, a 0 refinement sign indicating a positive sign and a refinement magnitude of 1.
For coefficient index 3 the refinement coefficient of the current layer is also 1. This is coded using a 1 refinement flag, a 0 refinement sign indicating a positive sign and a refinement magnitude of 1.
For coefficient index 4 the refinement coefficient of the current layer is −4. This is coded using a 1 refinement flag, a 1 refinement sign indicating a negative sign and a refinement magnitude of 4.
For coefficient index 5 the refinement coefficient of the current layer is 0. This is coded using a 0 refinement flag. No refinement sign or refinement magnitude is coded.
For coefficient index 6 the refinement coefficient of the current layer is 1. This is coded using a 1 refinement flag, a 0 refinement sign indicating positive sign and a refinement magnitude of 1.
Depending on the implementation of this refinement symbol coding, the refinement magnitude may be omitted by restricting the magnitude to 1. The refinement sign may be omitted by allowing only positive refinement coefficients. Those up to these three elements are coded in this VLC technique.
As previously noted, VLC coding of binary symbols tends to be inefficient. Each symbol requires one bit regardless of the probability of the coded symbols. A grouping approach may be employed in some implementations to improve compression efficiency. The grouping approach bundles several binary symbols of the same element into one new symbol. Symbols of the same element are expected to have almost equivalent probability of 0 or 1. A codeword is assigned to each possible bundled new symbol.
FIG. 3 illustrates an example of such a grouping of length 2. Grouped symbols 00 are coded as 0. Grouped symbols 01 are coded as 10. Grouped symbols 10 are coded as 110. Grouped symbols 11 are coded as 111. In the example of FIG. 3 0 is the most probable symbol. FIG. 3 illustrates an example 12 bit symbol set that can be coded using only 9 bits due to the grouping. Larger grouping lengths (such as 3, 4 or more) may be used to further improve the compression efficiency if the probability of the binary symbols is more biased.
FIG. 4 illustrates an example grouping with length 2 for refinement elements using the same example as illustrated in FIG. 2. FIG. 4 illustrates that symbols of the same element type are grouped and coded according to the grouping length. Any remaining ungrouped symbols of that element type are treated as fractional symbols. Such fractional symbols are coded individually. Thus FIG. 4 illustrates grouping the refinement flags into groups 10, 11 and 10 with a fractional symbol 1. FIG. 4 also illustrates grouping the refinement signs into groups 00 and 01 with a fractional symbol 0. Note the arithmetic data of the refinement magnitude is not grouped.
Fractional symbols worsen the compression efficiency because those symbols are not coded by more efficient VLC tables. In an ideal case, the symbols of one element type in the whole layer are coded at once to achieve the maximum compression efficiency because it minimizes the number of non-grouped fractional symbols. However, due to the demand for fine-grained scalability, the coefficients in one layer tend to be divided into smaller pieces depending on their frequency band. The lower frequency band has higher priority. Due to memory bandwidth restrictions each piece is further divided into smaller coding units based on their spatial location by smaller rectangular region called codeblock or macroblock. Therefore, there will be many coding units within one layer and each coding unit will contain few coefficients in actual implementation of quality scalable video coding technology. In these cases, there will be many fractional symbols causing compression inefficiency.
When fine-grained scalability is required, a refinement magnitude of only 0 or 1 should be allowed and the number of non-zero refinement coefficients should decrease. In this case, many coding units contain few symbols (i.e. 0 or 1) for the refinement sign. This creates many fractional symbols, which reduces compression efficiency.
Therefore, VLC based technique that codes the elements required for refinement of magnitude more efficiently without losing the functionality of image quality scalability would be desirable.